# 二叉树的最小深度。深度优先搜索
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 一般都是深度搜先搜索和广度优先搜索
        minHeight = 10**9
        if not root:    # 没有根节点为0
            return 0
        if not root.left and not root.right:
            return 1
        if root.left:   # 有左节点
            minHeight = min(minHeight, self.minDepth(root.left))
        if root.right:
            minHeight = min(minHeight, self.minDepth(root.right))
        return minHeight + 1

# 当然也可以采用广度优先搜索。广度搜先搜索遇到的第一个没有子节点的深度就是需要的结果
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = collections.deque([root])
        depth = 1
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if not node.left and not node.right:
                    return depth
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            depth = depth + 1
    return 0